#ifndef ROPE_DOT_H__
#define ROPE_DOT_H__

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define NO_COPY_THRESHHOLD 256

typedef uint32_t byte;

struct Rope;
typedef struct Rope Rope;

struct Rope
{
	size_t refcount;
	size_t length;

	enum
	{
		ROPE_CONCATENATION,
		ROPE_STRING
	} tag;

	union
	{
		struct
		{
			Rope* left;
			Rope* right;
		} concatenation;

		byte* bytes;
	} content;	
};

Rope* ralloc(size_t length, byte* bytes)
{
	Rope* r = malloc(sizeof(*r));

	if(r == NULL) return NULL;

	r->refcount = 1;
	r->tag = ROPE_STRING;
	r->length = length;
	r->content.bytes = bytes;

	return r;
}

void rfree(Rope* f)
{
	(f->refcount)--;

	if(f->refcount == 0)
	{
		if(f->tag == ROPE_CONCATENATION)
		{
			rfree(f->content.concatenation.left);
			rfree(f->content.concatenation.right);
		}

		else
		{
			assert(f->tag = ROPE_STRING);
			free(f->content.bytes);
		}

		free(f);
	}
}

inline Rope* rcopy(Rope* r)
{
	(r->refcount)++;
	return r;
}

inline size_t rlen(Rope* r)
{
	return r->length;
}

Rope* rcat(Rope* left, Rope* right)
{
	Rope* r = malloc(sizeof(*r));

	if(r == NULL) return NULL;

	r->refcount = 1;
	r->length = rlen(left) + rlen(right);

	if(r->length < NO_COPY_THRESHHOLD)
	{
		r->tag = ROPE_STRING;
		r->content.bytes = malloc(sizeof(byte) * r->length);

		if(r->content.bytes != NULL)
		{
			/* TODO Better handling for edge case where a concatenee is a
			   concatenation. */
			if(left->tag == ROPE_STRING && right->tag == ROPE_STRING)
			{
				memcpy(r->content.bytes,
					left->content.bytes,
					rlen(left) * sizeof(byte));

				memcpy(r->content.bytes + rlen(left),
					right->content.bytes,
					rlen(right) * sizeof(byte));

				return r;
			}

			free(r->content.bytes);
		}
	}

	r->tag = ROPE_CONCATENATION;
	r->content.concatenation.left = rcopy(left);
	r->content.concatenation.right = rcopy(right);
	
	return r;
}

byte rgetbyte(Rope* r, size_t index)
{
	if(r->tag == ROPE_STRING) return r->content.bytes[index];

	assert(r->tag == ROPE_CONCATENATION);

	return index < rlen(r->content.concatenation.left)
		? rgetbyte(r->content.concatenation.left,index)
		: rgetbyte(r->content.concatenation.right,
			index - rlen(r->content.concatenation.left));
}

// TODO Optimize.
int rcmp(Rope* left, Rope* right)
{
	size_t i;
	byte lbyte, rbyte;

	for(i = 0; i < (rlen(left) < rlen(right) ? rlen(left) : rlen(right)); i++)
	{
		lbyte = rgetbyte(left,i);
		rbyte = rgetbyte(right,i);

		if(lbyte < rbyte) return -1;
		if(lbyte > rbyte) return 1;
	}

	if(rlen(left) < rlen(right)) return -1;
	if(rlen(left) > rlen(right)) return 1;

	return 0;
}

#endif

